package a2023.a0307;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

/**
 * @author lenovo
 * @date 2023/3/7
 */
public class a {
    //示例 1：
    //
    //输入：expression = "{a,b}{c,{d,e}}"
    //输出：["ac","ad","ae","bc","bd","be"]
    //
    //示例 2：
    //
    //输入：expression = "{{a,z},a{b,c},{ab,z}}"
    //输出：["a","ab","ac","z"]
    //解释：输出中 不应 出现重复的组合结果。
    //
    //来源：力扣（LeetCode）
    //链接：https://leetcode.cn/problems/brace-expansion-ii
    //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    public static void main(String[] args) {
        System.out.println(braceExpansionII2("{a,b}{c,{d,e}}"));
    }

    public static List<String> braceExpansionII(String expression) {
        System.out.println(expression.length());
        System.out.println(expression.substring(6, 15));
        return null;
    }

    //遍历左括号,拿到第一个整体,{a,b} 与 {c,{d,e}}
    //递归{c,{d,e}} 拿到 c 与 {d,e}
    //拿到最小整体判断值与同一外层整体值计算后值 c , d , e 此时将其视为最小整体{c,d,e}
    //递归至最大整体
    public static String calculate(String s) {
        if (s.indexOf("{") <= 1) {
            return s;
        } else {
            int len = s.length();
            int num = 0;
            int left = 0;
            for (int i = 0; i < len; i++) {
                if (s.charAt(i) == '{') ++num;
                else if (s.charAt(i) == '}') --num;
                if (num == 1) {
                    left = i;
                } else if (num == 0) {
                    calculate(s.substring(left, i + 1));
                    //判断前面left一个是整体还是 ','
                    //组合成一个新的整体

                }
            }
        }
        return "";
    }


    private static TreeSet<String> s = new TreeSet<>();

    public static List<String> braceExpansionII2(String expression) {
        dfs(expression);
        return new ArrayList<>(s);
    }

    private static void dfs(String exp) {
        int j = exp.indexOf('}');
        if (j == -1) {
            s.add(exp);
            return;
        }
        int i = j;
        while (exp.charAt(i) != '{') {
            --i;
        }
        String a = exp.substring(0, i);
        String c = exp.substring(j + 1);
        for (String b : exp.substring(i + 1, j).split(",")) {
            dfs(a + b + c);
        }
    }

}
